#include <vector>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
// 合并两个有序链表
ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
{
    ListNode *retnode = new ListNode(0);
    ListNode *ret = retnode;
    while (list1 && list2)
    {
        if (list1->val < list2->val)
        {
            retnode->next = list1;
            list1 = list1->next;
        }
        else
        {
            retnode->next = list2;
            list2 = list2->next;
        }
        retnode = retnode->next;
    }
    if (list1)
    {
        retnode->next = list1;
    }
    if (list2)
    {
        retnode->next = list2;
    }
    return ret->next;
}
class Solution
{
public:
    // 思路：两两合并，直到只剩一个链表
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        if (lists.size() == 0)
            return nullptr;
        while (lists.size() > 1) // 直到只剩一个链表  例子：[[l1], [l2], [l3], [l4]] -> [[l1+l2], [l3+l4]] -> [[l1+l2+l3+l4]]
        {
            vector<ListNode *> tempList;              // 存储合并后的链表
            for (int i = 0; i < lists.size(); i += 2) // 两两合并  把l1和l2合并，l3和l4合并 然后lists就是[l1+l2, l3+l4]
            {
                ListNode *l1 = lists[i];  // 第一个链表
                ListNode *l2 = nullptr;   // 第二个链表:因为可能是奇数个链表，所以需要判断
                if (i + 1 < lists.size()) // 判断是否有第二个链表
                {
                    l2 = lists[i + 1];
                }
                tempList.push_back(mergeTwoLists(l1, l2)); // 合并两个链表并存储
            }
            // 更新链表数组
            lists = tempList; // lists = [l1+l2, l3+l4]
        }
        return lists[0];
    }
};